package sort;

import java.util.Arrays;

/**
 * Created by Administrator on 2018/2/27 0027.
 */
public class QuikSort
{
    public static void main(String[] args)
    {
        int[] NUMBERS = {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        quickSort(NUMBERS, 0, NUMBERS.length-1);
        System.out.println(Arrays.toString(NUMBERS));
    }

    private static void quickSort(int[] src, int lo, int hi)
    {
        if (lo >= hi)
        {
            return;
        }
        //进行第一轮排序获取分割点
        int index = partition(src, lo, hi);
        //排序前半部分
        quickSort(src, lo, index - 1);
        //排序后半部分
        quickSort(src, index + 1, hi);
    }

    private static int partition(int[] array, int lo, int hi)
    {
        /** 固定的切分方式 */
        int key = array[lo];//选取了基准点
        while (lo < hi)
        {
            //从后半部分向前扫描
            while (array[hi] >= key && hi > lo)
            {
                hi--;
            }
            array[lo] = array[hi];
            //从前半部分向后扫描
            while (array[lo] <= key && hi > lo)
            {
                lo++;
            }
            array[hi] = array[lo];
        }
        array[hi] = key;//最后把基准存入
        return hi;
    }
}
